package q581_findUnsortedSubarray;

public class Solution {
    /*
    最简单的方法是将数组排序后分别检查左侧和右侧从哪一位开始出现不同 然后计算中间长度即可
    但如果要实现o(n)时间复杂度以及O(1)的空间复杂 则需要如下方式：
    如果我们将数组分成三段 a b c 中间的b一段需要进行排序 那么可以预见的是 b的最小值大于a的最大值 b的最大值小于c的最小值
    所以 我们通过从左向右遍历 并维护一个最大值当出现一个更大的数的时候 就更新最大值 否则就更新边界
    这样的方式使得 当到达数组c的时候 每个数都会更新最大值 而不会更新边界 因此边界就停留在了b的最后一个数上
    同理可以得到b的第一个数的位置
    通过两个位置即可计算b的长度
    为了避免数组是已排序好的情况 只需要一开始将边界分别设计为 -1 和 0 即可 最后仍然能够通过计算 r - l + 1 来计算长度
     */
    public int findUnsortedSubarray(int[] nums) {
        int r = -1, l = 0, rMax = nums[0], lMin = nums[nums.length - 1];
        for (int i = 0; i < nums.length; i++) {
            if (rMax > nums[i]) {
                r = i;
            } else {
                rMax = nums[i];
            }
            
            if (lMin < nums[nums.length - 1 - i]) {
                l = nums.length - 1 - i;
            } else {
                lMin = nums[nums.length - 1 - i];
            }
        }

        return r - l + 1;
    }
}
